package com.labuladong;

/**
 *  凑零钱
 */
public class AddInTheChange {

    public static void main(String[] args) {
//        int[] coins={1,2,5};
//        int n = coinChange(coins, 11);
//        System.out.println(n);
        int [] temp=new int[11];
        int[] coins={1,2,5};
        int n = coinChange1(coins, 11,temp);
        System.out.println(n);
    }

    /**
     * 功能描述: 暴力解法
     * @author huipanxing huipanxing@chinasofti.com
     * @date 2021/11/3 14:06
     * @param coins
     * @param amount
     * @return int
     */
    public static int coinChange(int[] coins, int amount) {
        if (amount<0){
            return -1;
        }
        if (amount==0){
            return 0;
        }
        int res=Integer.MAX_VALUE;
        for (int i = 0; i < coins.length; i++) {
            int min = coinChange(coins, amount - coins[i]);
            if (min==-1){
                continue;
            }
            res=Math.min(res,min+1);
        }
        return res;
    }

    public static int coinChange1(int[] coins, int amount,int [] temp) {
        if (temp[amount-1]!=0){
            return temp[amount-1];
        }
        if (amount<0){
            return -1;
        }
        if (amount==0){
            return 0;
        }
        int res=Integer.MAX_VALUE;
        for (int i = 0; i < coins.length; i++) {
            int min = coinChange(coins, amount - coins[i]);
            if (min==-1){
                continue;
            }
            res=Math.min(res,min+1);
        }
        temp[amount-1]=res;
        return temp[amount-1];
    }
}
